#include<stdio.h>
#include<malloc.h>
struct node
{
    int no;
    struct node *next;
};


int size=0;
void append(struct node **p,int n)
{
    struct node *temp,*r;
    temp=*p;
    if(*p==NULL)
    {
        temp=malloc(sizeof(struct node));
        temp->no=n;
        temp->next=NULL;
        *p=temp;
	size=1;
        
        
    }
    else
    {
        temp=*p;
        while(temp->next!=NULL)
            temp=temp->next;
        r=malloc(sizeof(struct node));
        r->no=n;
        r->next=NULL;
        temp->next=r;
        size++;
        
    }
}
void insert(struct node *p,int n,int pos)
{
    int i;
    struct node *temp,*r;
    temp=p;
    for(i=0;i<pos-1;i++)
    {
        temp=temp->next;
        if(temp==NULL)
        {
            printf("there are less than %d elements in the list",pos);
        }
    }
    r=malloc(sizeof(struct node));
    r->no=n;
    r->next=temp->next;
    temp->next=r;
    size++;
}
void display(struct node *p)
{
    int a=0;
   
    if(p==NULL)
    {
        printf("no elements exists");
    }
    else
    {
        printf("[");
        while(p!=NULL)
        {
            printf("%d",p->no);
            p=p->next;
            
            if(a!=size-1)
            {
                printf(",");
            }
            else
            {
                printf("");
            }
	    a++;
        }
        printf("]");
    }
}
void remov(struct node **p,int num)
{
    struct node *cur,*prev;
    cur=*p;
    if(cur==NULL)
    {
        printf("list is empty and no element can be deleted");
    }
    
    else
    {
        for (cur =*p, prev = NULL;
	     cur != NULL && cur->no != num;
	     prev = cur, cur = cur->next);
        if(prev==NULL)
        {
            *p=(*p)->next;
            size--;
            //printf("there was only one element in the list ,now it has become empty\n");
        }
        else
        {
            prev->next=cur->next;
            free(cur);
            size--;
        }
    }
}
void pop(struct node **p)
{
        int ind,i,a=0;
        struct node *cur,*prev;
        
        cur=*p;
        if(cur==NULL)
        {
        printf("list is empty and no element can be deleted\n");
        }
        else
        {
            printf("enter the index of the no. to be deleted\n");
            printf("if u want to delete the last element enter '-1' \n");
            scanf("%d",&ind);
            if(ind>=size)
            {
                 printf("index is too high, highest index is\n %d\n",size-1);
            }
            else if(ind==-1)
            {
                 for (cur =*p, prev = NULL;
                     cur->next!= NULL;
                     prev = cur, cur = cur->next);
                 if(prev==NULL)
                    {
                        *p=(*p)->next;
                        size--;
                        //printf("there was only one element in the list ,now it has become empty\n");
                    }
                 else
                 {
                     prev->next=NULL;
                     free(cur);
                     size--;
                 }
            }
            else
            {
                for (cur =*p, prev = NULL;
                     cur != NULL && a!=ind;
                     prev = cur, cur = cur->next,a++);
                if(prev==NULL)
                    {
                        *p=(*p)->next;
                        size--;
                        //printf("there was only one element in the list ,now it has become empty\n");
                    }
                else
                {
                    
                        prev->next=cur->next;
                        free(cur);
                        size--;
                }
            }
        }
}
void indexing(struct node *p,int n)
{
    int l,flag=0,a=0;
    while(p!=NULL)
    {
        if(p->no==n)
        {
            l=a;
            flag=1;
            break;
        }
        a++;
        p=p->next;
    }
    if(flag==0)
	printf("element does not exist");
    else
	printf("the index is \n%d\n",l);
}
void count(struct node *p,int n)
{
    int a=0;
    while(p!=NULL)
    {
        if(p->no==n)
        {
            a++;
        }
        p=p->next;
    }
    printf("\n\n%d\n",a);
}
void sort(struct node *p)
{
	int temp;
	struct node *prev,*cur;
        
	
	prev=p;
	for(prev=p;prev->next!=NULL;prev=prev->next)
	{
		for(cur=prev->next;cur!=NULL;cur=cur->next)
		{
			if(prev->no > cur->no)
			{	temp=cur->no;
				cur->no=prev->no;
				prev->no=temp;
			}
		}
	}
}
void extend(struct node *p)
{
	char c='y';
	int n;
	do
	{
		printf("enter the element");
		scanf("%d",&n);
		append(&p,n);
		printf("enter 'y' to enter another element");
		scanf("%s",&c);
	}while(c=='y'||c=='Y');
}
void reverse(struct node **p)
{
    	struct node *temp,*n,*m;
   	m=NULL;
    	n=*p;
    	
    	while(n!=NULL)
	{
		temp=m;
		m=n;
		n=n->next;
		m->next=temp;
	}
	*p=m;
}
	
	
    
    
    

void main()
{
	
	
         char ch='y';
	 int n,no1,no2,in1,no3,no4,no5;
	 struct node *p;
	 p=NULL;
	 
	 do
	 {
	     printf("enter 1 to append an element\n");
	     printf("enter 2 to insert an element\n");
	     printf("enter 3 to remove an element\n");
	     printf("enter 4 to pop an element\n");
	     printf("enter 5 to find the index of an element\n");
	     printf("enter 6 to count the occurence of an element\n");
	     printf("enter 7 to display the list of element\n");
	     printf("enter 8 to reverse  the list\n");
	     printf("enter 9 to extend the list of  elements\n");
	     printf("enter 10 to sort the list of elements\n");
	    
	     printf("please enter ur choice");
	     scanf("%d",&n);
	     switch(n)
	     {
		 case 1:
		     printf("enter the element u want to append in the list\n");
		     scanf("%d",&no1);
		     append(&p,no1);
		     break;
		 case 2:
		     printf("enter the element u want to insert in the list\n");
		     scanf("%d",&no2);
		     printf("enter the index where u want to insert the element in the list\n");
		     printf("remember index starts from 0");

		     scanf("%d",&in1);
		     insert(p,no2,in1);
		     break;
		 case 3:
		     printf("enter the element u want to remove from the list\n");
		     scanf("%d",&no3);
		     remov(&p,no3);
		     break;
		 case 4:
		     pop(&p);
		     break;
		 case 5:
		     printf("enter the element whose index  u want to know\n");
		     printf("rememember only the index of first ocurence of the no. is given");
		     scanf("%d",&no4);
		     indexing(p,no4);
		     break;
		 case 6:
		     printf("enter the element in the list whose no. of occurences in the list iu want to know\n");
		     scanf("%d",&no5);
                     count(p,no5);
		     break;
		 case 7:
		     printf("here are the elements in the list \n");
		     display(p);
		     break;
		 case 8:
		     printf("here is the reverse of the list\n");
		     printf("now the list has become the reversed list,further opereation will be performed on it only\n");
		     reverse(&p);
		     break;
		case 9:
		     
		     extend(p);
		     break;
		case 10:
		     sort(p);
		     break;
		
                default : printf("please only enter the no. of the choices provided\n");
                          break;
            }
            printf("do u wnt to continue (y/n)");
            scanf("%s",&ch);
            if(ch=='y'||ch=='Y')
            {
		system("clear");
            }
        }while(ch=='y'||ch=='Y');
                 
                     
                 
             


}	
		
	

	
	
	


    

                       

    
        
    
    
